Podróż

Limit pamięci: 32 MB

Rozważmy graf opisujący sieć komunikacji publicznej, np. sieć autobusową, tramwajową, metra, itp. Wierzchołki grafu, o numerach , reprezentują przystanki, a krawędzie , (dla ) oznaczają możliwe, bezpośrednie przejazdy od przystanku do ().

W sieci kursują pojazdy linii komunikacyjnych. Linie komunikacyjne oznaczone są numerami . Linia komunikacyjna zdefiniowana jest przez ciąg przystanków , przez które przejeżdżają pojazdy linii, oraz czasy przejazdów pomiędzy przystankami - jest czasem przejazdu od przystanku do , lub z powrotem, tj. od przystanku do ; jest czasem przejazdu od przystanku do , itd. Wszystkie przystanki linii są różne, tj. dla zachodzi .

Na danej linii pojazdy kursują z określoną częstotliwością , gdzie jest liczbą ze zbioru . Pojazdy linii wyruszają z przystanku o każdej "okrągłej" godzinie doby, , (), a następnie zgodnie z częstotliwością linii, a więc o godzinach , , ... itd. ( oznacza " minut po godzinie "). Ruch pojazdów linii odbywa się jednocześnie w obu kierunkach: z przystanku do , a także z przystanku do . Godziny odjazdów pojazdów linii z przystanku są takie same, jak z przystanku .

W tak zdefiniowanej sieci komunikacji publicznej chcemy odbyć podróż z przystanku początkowego , do przystanku końcowego . Zakładamy, że podróż jest możliwa i nie będzie trwała dłużej niż 24 godziny. W trakcie podróży możemy się przesiadać dowolną liczbę razy z jednej linii komunikacyjnej na inną. Przyjmujemy, że czas dokonania przesiadki jest równy 0, jednakowoż, zmieniając linię musimy liczyć się z koniecznością czekania na pojazd linii, do którego chcemy się przesiąść. Naszym celem jest odbycie podróży z przystanku początkowego , do przystanku końcowego , w minimalnym czasie.

Przykład

Na poniższym rysunku przedstawiono schemat sieci komunikacyjnej o 6 przystankach i dwóch liniach: 1 i 2. Pojazdy linii 1 kursują pomiędzy przystankami 1, 3, 4 i 6, a linii 2 pomiędzy przystankami 2, 4, 3 i 5. Częstotliwości kursowania pojazdów linii wynoszą, odpowiednio, oraz . Czasy przejazdów pomiędzy przystankami umieszczono obok krawędzi sieci opatrując je indeksami 1 i 2 dla poszczególnych linii.

Załóżmy, że o godzinie 23:30 znajdujemy się na przystanku początkowym 5 i chcemy odbyć podróż do przystanku końcowego 6. Wówczas musimy odczekać 10 minut i o godzinie 23:40 wyjeżdżamy linią 2. Nasza podróż może mieć dwa warianty. W pierwszym wariancie, po dojechaniu do przystanku 3 o godzinie 23:51 i odczekaniu 3 minut, przesiadamy się o godzinie 23:54 na linię 1 i dojeżdżamy do przystanku 6 o godzinie 0:16 (następnego dnia). W drugim wariancie, dojeżdżamy linią 2 do przystanku 4 o godzinie 0:8, czekamy 13 minut i o godzinie 0:21 wsiadamy do pojazdu linii 1, osiągając przystanek końcowy 6 o godzinie 0:31. Tak więc najwcześniej możemy dotrzeć do przystanku 6 o godzinie 0:16.

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia opis sieci oraz linii komunikacyjnych, numer przystanku początkowego , numer przystanku końcowego , godzinę początkową oraz minuty początkowe ,
• wyznaczy minimalny czas podróży od przystanku początkowego , do przystanku końcowego ,
• wypisze na standardowe wyjście najwcześniejszą możliwą godzinę z minutami dotarcia do przystanku - odpowiednio, oraz .

Wejście

W pierwszym wierszu standardowego wejścia zapisanych jest sześć liczb całkowitych, pooddzielanych pojedynczymi odstępami:

• liczba przystanków (),
• liczba linii komunikacyjnych (),
• numer przystanku początkowego (),
• numer przystanku końcowego (),
• godzina rozpoczęcia podróży (),
• minuta rozpoczęcia podróży ().

W kolejnych wierszach opisane są kolejne linie komunikacyjne - opis każdej linii zajmuje trzy kolejne wiersze.

• W pierwszym wierszu opisującym linię komunikacyjną są zapisane dwie liczby całkowite, oddzielone pojedynczym odstępem: , równa liczbie przystanków (), oraz , równa częstotliwości kursowania pojazdów ().
• W drugim wierszu opisującym linię komunikacyjną jest zapisanych różnych liczb całkowitych, pooddzielanych pojedynczymi odstępami: - numery kolejnych przystanków na tej linii (, dla ).
• W trzecim wierszu opisującym linię komunikacyjną jest zapisanych liczb całkowitych, pooddzielanych pojedynczymi odstępami: - czasy przejazdów (w minutach) pomiędzy kolejnymi przystankami na tej linii (, dla ).

Suma liczb przystanków, na wszystkich liniach razem, nie przekracza (tzn. ).

Wyjście

Twój program powinien zapisać w pierwszym i jedynym wierszu standardowego wyjścia dwie liczby całkowite oddzielone pojedynczym odstępem: godzinę dotarcia do przystanku końcowego () oraz minutę dotarcia do przystanku końcowego ().

Przykład

Dla danych wejściowych:

6 2 5 6 23 30
4 15
1 3 4 6
9 12 10
4 20
5 3 4 2
11 17 11

poprawną odpowiedzią jest:

0 16

Autor zadania: Zbigniew J. Czech.